Field of the Disclosure
The present disclosure relates generally to processing systems and, more particularly, to scheduling tasks for execution in processing systems.
Description of the Related Art
Processing systems can include more than one processor core to execute instructions concurrently or in parallel. For example, the central processing units (CPUs) in personal computers frequently include four or more processor cores, servers can implement numerous CPUs, and computing clusters are formed of numerous interconnected servers. Schedulers attempt to maximize the performance of these entities, e.g., by scheduling different tasks of one or more programs to run concurrently on different processor cores to minimize the total execution time of the programs. However, schedulers are not able to predict precisely how long it will take a processor core to complete execution of a scheduled thread or task. Thus, load imbalances may occur in which some processor cores may remain idle while other processor cores have a backlog of scheduled tasks waiting to be completed. For example, procedures that are scheduled for execution by a processor during a multithreaded computation may include a parent thread that spawns one or more child threads, which provide return values to successor threads that are also spawned by the parent thread. The processor must therefore execute the child thread to return a value to the successor thread before the procedure can make additional progress. The total execution time of the procedure may therefore depend on the number of generations of child threads, which may be difficult to predict accurately.